package com.fw.leetcode.linkedlist;

import com.fw.leetcode.LeetCode;

/**
 * 24. Swap Nodes in Pairs
 *
 * Given a linked list, swap every two adjacent nodes and return its head.
 * You must solve the problem without modifying the values in the list's nodes
 * (i.e., only nodes themselves may be changed.)
 *
 * Example 1:
 *  Input: head = [1,2,3,4]
 *  Output: [2,1,4,3]
 *
 * Example 2:
 *  Input: head = []
 *  Output: []
 *
 * Example 3:
 *  Input: head = [1]
 *  Output: [1]
 *
 * Constraints:
 *  The number of nodes in the list is in the range [0, 100].
 *  0 <= Node.val <= 100
 */
public class Num_0024 implements LeetCode {
    private interface Solution extends LinkedList {
        ListNode swapPairs(ListNode head);

        default void assertExpected(int[] head, int[] expected) {
            if (!assertEquals(swapPairs(build(head)), build(expected))) {
                swapPairs(build(head));
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public ListNode swapPairs(ListNode head) { // 最优：一次遍历（cur指针交换一次默认后移一位）：时O(n) 空O(1)
            /*
             * 两两交换链表节点
             *     header -> [1,2,3,4,5]
             *        ↑       ↑
             * 1:  header -> [2,1,3,4,5]
             *        ↑         ↑
             *     header -> [2,1,3,4,5]
             *                  ↑ ↑
             * 2:  header -> [2,1,4,3,5]
             *                  ↑   ↑
             *     header -> [2,1,4,3,5]
             *                      ↑ ↑
             */
            ListNode header = new ListNode(-1, head); // 建立辅助头节点
            ListNode prev = header;
            ListNode cur = prev.next;
            while (cur != null && cur.next != null) {
                // 存在连续的两个，则交换
                ListNode curNextNext = cur.next.next;
                cur.next.next = prev.next;
                prev.next = cur.next;
                cur.next = curNextNext;
                // 交换完成后，cur 默认后移一位
                prev = cur; // prev 后移两位，即当前 cur
                cur = cur.next; // cur 后移两位，即再后移一位
            }
            return header.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new int[]{1,2,3,4}, new int[]{2,1,4,3});
        solution.assertExpected(new int[]{}, new int[]{});
        solution.assertExpected(new int[]{1}, new int[]{1});
    }
}
